package map;

import org.junit.Test;

import java.util.HashMap;

/**
 * Map中key用Set来存放，不允许重复，即同一个Map对象所对应的类，必须重写hashCode()和equals()方法
 * > HashMap中的所有的key彼此间是不可重复的、无序的。所有的key就构成一个Set集合。
 * > HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。--->value所在类要重写equals()
 * > HashMap中的一个key-value就构成一个entry。
 * > HashMap中的所有的entry彼此之间是不可重复的、无序的。所有的entry就构成一个Set集合。
 */
public class MapTest {
    @Test
    public void testHashMapJDK7() {
        // 创建对象的过程中，底层会初始化数组Entry[] table = new Entry[16];
        HashMap<Integer, String> map = new HashMap<>();

        map.put(1, "AA"); // 1 和 "AA" 封装到一个Entry对象中，考虑将此对象添加到table数组中。
        map.put(2, "BB");
        
        // ...
        /*
        添加/修改过程

        将(key1, value1)添加到当前的map中：
            首先需要调用key1所在类的hashCode()方法，计算key1对应的哈希值1，此哈希值1经过某种计算(hash())后，得到哈希值2.
            哈希值2再经过某种算法(indexFor())之后，就确定了其在数组table中的索引位置i。
            （情况1） 1.1 如果此索引位置i的数组上没有元素，就确定了(key1, value1)在数组table中的索引位置i。
             1.2 如果此索引位置i的数组上有元素(key2,value2)，则需要继续比较key1和key2的哈希值2；--> 哈希冲突
                （情况2）2.1 如果key1的哈希值2与key2的哈希值2不相同，则(key1,value1)添加成功。
                2.2 如果key1的哈希值2与key2的哈希值2相同，则需要继续比较key1和key2的equals().要调用key1所在类的equals(key2);
                    （情况3） 3.1 调用equals()返回false：则(key1, value1)添加成功。
                    3.2 调用equals()返回true：则认为key1, key2是相同的。默认情况下，value1替换原有的value2.
         说明：情况1：将(key1, value1)存放到数组的索引i的位置；
              情况2、3：(单向链表结构)将新键值对以链表节点形式追加到该索引位置的链表末尾（JDK 1.7 前是头插法，JDK 1.8+ 改为尾插法）

         随着不断添加元素，在满足如下的条件的情况下，会考虑扩容：
         (size >= threshold && null != table[i])
         当元素个数达到临界值( -> 数组的长度 * 加载因子)时，就考虑扩容。
         默认的临界值 = 16 * 0.75  ---> 12
         默认扩容为原来的2倍。
         */

        System.out.println(map);
    }

    @Test
    public void testHashMapJDK8() {
        /*
         1. jdk8 当创建了HashMap实例后，底层并没有初始化table数组。
         当数组添加(key, value)时，进行判断，如果发现table尚未被初始化，则对数组进行初始化。
         2. HashMap底层定义了Node内部类，替换jdk7中的Entry内部类。意味着，创建的数组是Node[]
         3. 如果当前的(key, value)经过一系列判断之后，可以添加到当前的数组角标 i 中。
         如果此时角标 i 位置上有元素。旧的元素指向新的(key, value)元素。（尾插法）
         4. jdk7：数组+单向链表
            jdk8：数组+单向链表+红黑树
            什么时候会使用单向链表变为红黑树：
                如果数组索引i位置上的元素个数达到8，并且数组的长单独达到64，就将此索引i位置上的多个元素改为使用红黑树的结构进行存储。
                （红黑树进行put()/get()/remove()操作的时间复杂度为O(log n),比单向链表的时间复杂度O(n)好。性能更高。）
            什么时候会使用红黑树变为单向链表
                当使用红黑树的索引i位置上的元素个数低于6时，就会将红黑树结构退化为单向链表。
                Because TreeNodes are about twice the size of regular nodes,
                we use them only when bins contain enough nodes to warrant use
                (see TREEIFY_THRESHOLD).
         */

    }
}
